package leetcode_700;

import helpclass.TreeNode;

/**
 *@author 周杨
 *SecondMinimumNodeInABinaryTree_671 给定一颗特殊的树 求其节点里第二小的节点
 *describe:递归遍历即可 AC 100%
 *2018年10月5日 下午4:22:56
 */
public class SecondMinimumNodeInABinaryTree_671 {
	Integer max=null;//最小的 
	Integer second=null;//第二小的
	
	public static void main(String[] args) {
		SecondMinimumNodeInABinaryTree_671 test=new SecondMinimumNodeInABinaryTree_671();
		TreeNode root=new TreeNode(5);
		root.left=new TreeNode(5);
		root.right=new TreeNode(6);
		test.findSecondMinimumValue(root);
	}
	
	public int findSecondMinimumValue(TreeNode root) {
        help(root);
        if(second==null)
        	return -1;
        else
        	return second;
    }
	public void help(TreeNode root) {
		if(root==null)
			return ;
		int min;
		if(root.left==null) {//没有儿子
			min=root.val;
		}
		else
			min=Math.min(root.left.val, root.right.val);
		if(max!=null) {
			if(min==max) {//说明该值遍历过 那么不予理会
				help(root.left);
				help(root.right);
				return;
			}
			if(min<max) {//如果该值比第二小的还小
				second=max;
				max=min;
			}
			else if(second!=null) {
				if(second>min) {
					second=min;
				}
			}
			else {
				second=min;
			}
		}
		else {
			max=min;
		}
		help(root.left);
		help(root.right);
	}
}
